1. Field of the Invention
The present invention is directed generally toward the domain of network resource management where the message bearing substrate for a multiplicity of transmitters sited at or near the edge of the network has limited bandwidth and does not support a practical carrier sense mechanism. An example of such a network is the electrical distribution grid. In such a network, if two or more transmitted messages overlap in time (collide) on the same bearer channel, neither message is decipherable at its destination. Slotted protocols, where every transmitter is allocated specific times wherein it is permitted to transmit, can maximize the utilization of such network. However, collisions are prevented only if the time clocks on every transmitter are precisely synchronized with one another. It is understood that “precisely” means to have a known tolerance as opposed to “exactly.” The present invention describes a system and diverse methods for synchronizing endpoints on such a network.
2. Background of the Invention
The electrical grid in the United States and most other areas of the world is historically divided into two networks: the transmission grid and the distribution grid. The transmission grid originates at a generation point, such as a coal-burning or atomic power plant, or a hydroelectric generator at a dam. Power is generated, and transmitted to distribution points, called distribution substations, via a highly controlled and regulated, redundant, and thoroughly instrumented high voltage network which has at its edge a collection of distribution substations. Over the last century, as the use of electrical power became more ubiquitous and more essential, and as a complex market in the trading and sharing of electrical power emerged, the technology of the transmission grid largely kept pace with the technological requirements of the market.
The second network, the distribution grid, is the portion of the electrical grid that originates at the distribution substations and has at its edge a collection of residential, commercial, and industrial consumers of energy. In contrast to the transmission grid, the technology of the distribution grid has remained relatively static since the mid-1930s until very recent years. Today, as concern grows over the environmental effects of fossil fuel usage and the depletion of non-renewable energy sources, interest has increased in augmenting the electrical distribution grid with communication instruments. The primary goals of this activity are energy-related goals such as energy conservation, resource conservation, cost containment, and continuity of service.
It is desirable when so augmenting the distribution grid with communication instruments to employ the grid itself as the communication medium. The medium-voltage (>1 KV) power lines that comprise the bulk of the distribution grid discourage tampering, snooping, and spooling. Public utilities in the United States are subject to a statutory accounting model that favors capital investment over facilities costs, and so would rather communicate via the grid, a network they own, than the Internet or other wide-area wired or wireless network infrastructure, which they must lease or for which they pay usage charges. Finally, using the grid as the communication medium enables a mechanism that allows the network to infer the schematic location of the transmitter on the grid from characteristics of the received signal at another location on the grid. This capability has high value to utilities for applications such as fault isolation, energy optimization, and recovery management. Finally, the electrical grid is (reflexively) always present where instrumentation of the grid is needed, whereas nearly all utilities encounter situations where conditions do not support the use of other types of networks, or where the cost of other network types is prohibitive.
Some characteristics of the electrical grid are greatly different from other networks. First, as in many wireless applications, but not in other wired applications such as Ethernet, there is no carrier sense. In other words, one transmitter will generally not be able to know if another transmitter is transmitting on the same channel it wishes to use. If two transmitters attempt to use the same channel simultaneously, neither signal will be correctly received. Second, the data rate achievable using the power grid as a transmission medium is low compared to modern fiber or wireless networks. Finally, the network is hierarchical in structure and asymmetrical in transmission cost. It is much easier and cheaper to transmit from low voltage to high voltage on the electrical distribution grid than from high voltage to low voltage.
Despite these apparently limiting characteristics of the medium, the high value of the enabled applications, especially inferring the schematic location of the transmitter, drives the development of systems and methods for maximizing the utilization of a network with these characteristics. While the desire to use the electrical distribution grid as the network substrate is described in one aspect of the present invention, it must be noted that other network media have similar characteristics. There is nothing about the present invention that limits its application to only the electrical distribution grid.
Most conventional networks take advantage of the stochastic nature of transmission patterns. Transmissions from the edge of the network are initiated unpredictably and infrequently, from any specific transmitter, with respect to the data rate of which the conventional network is capable. The actual utilization of the network, expressed as a percentage of the maximum achievable data rate if one transmitter sent continuously over every available distinct path, is low. These networks, such as the Internet, are optimized for high response time at the expense of lower throughput. Conversely, in data collection networks of the type, topology, and other characteristics described herein, it is both feasible and desirable to drive throughput (and utilization) as close to 100% as possible, when measuring transmissions from the edge of the network to a central data collection point.
It is well known in the art that if it is possible to predict how much data an endpoint (or edge device) will transmit, and how frequently transmissions must occur, then the most efficient type of network protocol is one called a slotted protocol. In a pure slotted protocol, each edge device is assigned a specific set of times and durations, applied on a cyclical basis, when it is permitted to transmit. These times and durations, called slots, are assigned in such a way that a transmission from on edge device never collides with a transmission from any other edge device using the same physical and frequency-based channel. In this model, the theoretical edge-to-hub network utilization achievable is 100% with no message loss.
The theoretical utilization can only be approached if the system clocks on every edge device are precisely synchronized. In the simplest case, this is accomplished by having all the edge devices able to receive a broadcast timing pulse that each device receives simultaneously. This is not always easy to achieve even in high-bandwidth two-way networks, with the result that prior-art algorithms such as the Network Time Protocol (NTP) have been invented to compensate for network latency variations in receiving timing signals. However, NTP is usually not a feasible solution in the special type of network described herein, because it requires too much two-way communication.